package algorithms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class ParallelQuickSort extends RecursiveAction implements SortStrategy {
    private int[] data;
    private int l;
    private int r;
    private int[] ret;
    private static final int THRESHOLD=16;
//    private ForkJoinPool pool;

    public ParallelQuickSort() {
        ;
    }

    public ParallelQuickSort(int[] data, int l, int r) {
        this.data = data;
        this.l = l;
        this.r = r;
    }

    public int[] sort(int[] data) {
        // 排序所调用的方法
        this.data = data.clone();
        this.ret = new int[this.data.length];

        ForkJoinPool pool = new ForkJoinPool();

        ParallelQuickSort task = new ParallelQuickSort(this.data, 0, this.data.length-1);
        pool.invoke(task);
        return this.data;
    }

    public void compute() {
        // 线程的计算任务
        if (this.l >= this.r) return;
        else if (this.r - this.l <= THRESHOLD) {
            // 在r-l小于一定阈值时调用串行排序
            quickSort(l, r);
            return;
        }
        int q = _partition();

        List<RecursiveAction> tasks = new ArrayList<RecursiveAction>();
        ParallelQuickSort worker1 = new ParallelQuickSort(this.data, this.l, q-1);
        ParallelQuickSort worker2 = new ParallelQuickSort(this.data, q+1, this.r);
        tasks.add(worker1);
        tasks.add(worker2);
        invokeAll(tasks);
    }

    public int _partition() {
        int q = this.l;
        int pivot = this.data[this.r];
        for (int index=this.l; index<this.r; index++) {
            if (this.data[index] < pivot) {
                int tmp = this.data[index];
                this.data[index] = this.data[q];
                this.data[q] = tmp;
                q++;
            }
        }
        int tmp = this.data[q];
        this.data[q] = this.data[this.r];
        this.data[this.r] = tmp;

        return q;
    }

    public void quickSort(int l, int r) {
        // 串行排序算法，在r-l小于一定阈值时调用串行排序
        if (l>=r) return;
        int q = l;
        int pivot = this.data[r];
        for (int index=l; index<r; index++) {
            if (this.data[index] < pivot) {
                int tmp = this.data[index];
                this.data[index] = this.data[q];
                this.data[q] = tmp;
                q++;
            }
        }
        int tmp = this.data[q];
        this.data[q] = this.data[r];
        this.data[r] = tmp;

        quickSort(l, q-1);
        quickSort(q+1, r);
    }
}
